package me.algo.lst;

import java.util.Objects;
import java.util.PriorityQueue;

/**
 * @author guozheng
 * @date 2024/4/17
 */
public class L3 {
    public static void main(String[] args) {

    }

    /**
     * 148. 排序链表
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * @param head
     * @return
     */
    static public ListNode sortList(ListNode head) {
        if (Objects.isNull(head) || head.next == null) {
            return head;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>((o1, o2) -> {
            if (o1.val > o2.val) {
                return 1;
            } else if (o1.val == o2.val) {
                return 0;
            }
            return -1;
        });
        ListNode cur = head;
        while (cur != null) {
            heap.add(cur);
            cur = cur.next;
        }
        ListNode dummy = new ListNode();
        ListNode rcu = dummy;
        while (!heap.isEmpty()) {
            ListNode nd = heap.remove();
            nd.next = null;
            rcu.next = nd;
            rcu = rcu.next;
        }
        return dummy.next;
    }
}
